#include<iostream>
using namespace std;
long long c[200000],f[200000],e[200000],pre[200000];
int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int t;
    cin>>t;
    for(int z=0;z<t;z++){
        int a;
        cin>>a;
        for(int b=0;b<a;b++){
            cin>>c[b];
            f[b]=0;
            int p=-1;
            for(int d=b-1;d>=0;d--){
                if(c[d]==c[b]){
                    p=d;
                    break;
                }
            }
            if(p!=-1){
                long long all=0;
                for(int z=p+1;z<b;z++){
                    if(e[z]==e[p] && pre[z]<p){
                        all+=f[z];
                    }
                }
                if(all<=c[b]){
                    e[b]=e[z];
                    for(int z=p+1;z<b;z++){
                        e[z]=3-e[z];
                    }
                    f[b]=c[b];
                    pre[b]=p;
                }else{
                    pre[b]=-1;
                }
            }else{
                e[b]=1;
                pre[b]=-1;
            }
        }
        long long all=0;
        for(int p=0;p<a;p++){
            all+=f[p];
        }
        cout<<all<<endl;
    }
    return 0;
}
